package com.MSofLectures.Tool;

import java.util.Stack;

public class Sorter {
	/*
	 * @author ufo
	 * 非递归快速排序
	 */
	static public void quickSort(Object[] target, Comparer comparer) {
		if (null == target || 0 == target.length)
			return;
		Stack<Integer> startStack = new Stack<Integer>();
		Stack<Integer> endStack = new Stack<Integer>();
		int start = 0;
		int end = target.length - 1;
		int pivotPos;

		startStack.push(start);
		endStack.push(end);
		while (!startStack.isEmpty()) {
			start = startStack.pop();
			end = endStack.pop();
			pivotPos = partition(target, start, end,comparer);
			if (start < pivotPos - 1) {
				startStack.push(start);
				endStack.push(pivotPos - 1);
			}
			if (end > pivotPos + 1) {
				startStack.push(pivotPos + 1);
				endStack.push(end);
			}
		}
	}

	private static int partition(Object[] target, int start, int end, Comparer comparer) {// 分块方法，在数组a中，对下标从start到end的数列进行划分
		Object pivot = target[start]; // 把比pivot(初始的pivot=a[start]小的数移动到pivot的左边
		while (start < end) { // 把比pivot大的数移动到pivot的右边
			while (start < end && comparer.compare(target[end], pivot))
				end--;
			target[start] = target[end];
			while (start < end && comparer.compare(pivot, target[start]))
				start++;
			target[end] = target[start];
		}
		target[start] = pivot;
		return start;// 返回划分后的pivot的位置
		// printArray(a);
	}

	static public boolean isBigerThan(int a, int b) {
		return a > b;
	}

	static public boolean isSmallerThan(int a, int b) {
		return a < b;
	}
}
